package leetcode.D300.T210;

import java.util.*;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-17 12:54:13 星期四
 */

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Set<Integer>[] fromGraph = buildFromGraph(numCourses, prerequisites);
        Set<Integer>[] toGraph = buildToGraph(numCourses, prerequisites);
        Set<Integer> cand = new HashSet<>();
        for(int i=0; i<fromGraph.length; ++i) {
            if (fromGraph[i].isEmpty())
                cand.add(i);
        }
        Deque<Integer> st = new LinkedList<>();
        for (int v : cand) {
            st.push(v);
        }
        cand.clear();

        int k = 0;
        int[] order = new int[numCourses];
        while (!st.isEmpty()) {
            int top = st.pop();
            order[k++] = top;
            Iterator<Integer> it = toGraph[top].iterator();
            while (it.hasNext()) {
                int v = it.next();
                fromGraph[v].remove(top);
                if (fromGraph[v].isEmpty())
                    cand.add(v);
            }
            for (int v : cand) {
                st.push(v);
            }
            cand.clear();
        }
        if (k < numCourses)
            return new int[]{};
        else
            return order;
    }

    private Set<Integer>[] buildFromGraph(int numCourses, int[][] prerequisites) {
        Set<Integer>[] graph = new Set[numCourses];
        for (int i=0; i<numCourses; i++)
            graph[i] = new HashSet<Integer>();
        for(int i=0; i<prerequisites.length; ++i) {
            int to = prerequisites[i][0], from = prerequisites[i][1];
            graph[to].add(from);
        }
        return graph;
    }

    private Set<Integer>[] buildToGraph(int numCourses, int[][] prerequisites) {
        Set<Integer>[] graph = new Set[numCourses];
        for (int i=0; i<numCourses; i++)
            graph[i] = new HashSet<Integer>();
        for(int i=0; i<prerequisites.length; ++i) {
            int to = prerequisites[i][0], from = prerequisites[i][1];
            graph[from].add(to);
        }
        return graph;
    }
}